1. Field of the Invention
Disclosed herein is a method and apparatus for image retrieval which uses a multi-scale edge representation of images. Through the use of this invention, images such as digitally encoded photographs, CAD design drawings, and video scenes, can be categorized for fast retrieval. The retrieval is effected by providing a sketch or image having characteristic edges; images are retrieved and presented in the order of their similarity to the provided sketch or image. This invention is particularly applicable to image retrieval from large image databases, such as photographic archives, digital libraries, catalogs, and videos.
2. Description of Related Art
Various techniques are commonly employed for retrieving images stored in a database. The most conventional technique for storing and retrieving images which match a desired characteristic is to associated key words with each images, such as "portrait", "seascape", "mountain", "presidents", etc. Having associated such key words to the images, a user provides one or more search words to the search or retrieval system, and the system presents one or more images in dependence upon the degree of correspondence between the search words and stored key words. Conventional Internet search engines are examples of such text based retrieval means.
Graphics based retrieval is a more intuitive approach to image retrieval. Conventional graphic based retrieval systems employ various forms of color or pattern matching. Typically, the user provides a sample image, and the system retrieves images having similar patterns of color. For example, by providing an image of a seascape, the retrieved images would be those with blue or green colors at their bottom, beige or brown colors in the middle, and blue/white colors at the top. Conventional pattern matching techniques may also be utilized. For example, images may be categorized as containing recognizable patterns, such as a mix of upright triangles for mountain scenes, circles and rectangles for body shapes, etc. A target image of a circle amongst triangles would retrieve, for example, a photograph of a person's head with mountains in the background; four circles in a rectangle might retrieve a photograph of Mount Rushmore; etc.
Formal algorithmic approaches are also utilized. In [1], the user provides a sketch, a drawing, or a detailed image, and the image retrieval is accomplished by comparing the sketch to each image in the database, at an abstract level. Associated with each data base image is an icon, which is a graphical abstraction of the actual image. A target icon is formed from the graphical abstraction of the user provided target image. Each data base image icon is compared to the target image icon by computing the degree of local and global correlation between the icons; the images associated with the icons having the strongest correlation are presented to the user.
These existing image retrieval methods require a significant amount of analysis and computation during the retrieval process, making image retrieval by graphic example significantly less efficient than text based retrieval techniques. Text based image retrieval, however, requires the categorizing of each picture by keywords, which can be a burdensome process if applied to hundreds or thousands of images; also, the individual choice of keywords limits the effectiveness of the search to the degree of correspondence between the words the categorizer used to describe the stored images, and the words the searcher uses to describe the desired image. Pattern based systems require the predefinition of characteristic patterns, and the search efficiency and effectiveness is directly related to the diversity of these characteristic patterns among the images in the database.